// https://leetcode.cn/problems/reverse-linked-list/

package leet206reverselinkedlist

// 思路：
// 1. 定义一个prev指针，初始值为nil
// 2. 定义一个current指针，初始值为head
// 3. 遍历链表，直到current为nil
// 4. 在每次迭代中，先保存current的下一个节点next临时存储为tmp
// 5. 将current的前进指针修改指向到prev
// 6. 将prev指针移动到current节点
// 7. 将current指针移动到下一个节点tmp
// 8. 当current为nil时，prev指针即为反转后的链表头节点
// 9. 返回prev指针
// 10. 时间复杂度O(n)，空间复杂度O(1)
// 11. 注意：head节点可能为nil，所以要先判断head是否为nil
// 其实这也是一个双指针的思路。
type ListNode struct {
	Val  int
	Next *ListNode
}
func reverseList(head *ListNode) *ListNode {
	if head == nil {
		return nil
	}
	prev := (*ListNode)(nil)
	current := head
	for current != nil {
		// 临时保存下一个节点，并修改current的前进指针为反方向
		tmp := current.Next
		current.Next = prev
		// 向前平移 prev 和 current
		prev = current
		current = tmp
	}
	return prev
}